package com.mamingchao.foundation.tree.heap;

import com.mamingchao.foundation.arraysort.Sortable;

import java.util.Objects;

/**
 * Created by mamingchao on 2024/5/23.
 */
public class HeapSort implements Sortable {

    private void maxRootValueHeapSort(int[] arr){
        if (!Objects.nonNull(arr) || arr.length ==0) {
            return;
        }
        // 分两步，第一步，先把无序的数组，顺序调整为大根堆（当然小根堆也可以；大小根堆没啥区别）
        for (int i = 1; i < arr.length; i++) {
            heapInsert(arr, i);
        }

        // 第一步还有个优化的方法；从下而上

        // 第二步，拿走root value，然后执行heapify，把拿走了root 的剩余元素继续调整为大根堆

        // heapifyUtil.heapify()
    }


    private void heapInsert(int[] arr, int appendNodeIndex){
        int parentNodeIndex = (appendNodeIndex-1)/2;
        while (appendNodeIndex !=0 && arr[appendNodeIndex] > arr[parentNodeIndex]) {
            swap(arr, appendNodeIndex, parentNodeIndex);
            appendNodeIndex = parentNodeIndex;
        }
    }




    @Override
    public void sort(int[] arr, int start, int end) {

    }
}
